import random  # 导入随机模块
import math    # 导入数学模块

def assign_cluster(x, c):
    min_dist = float('inf')  # 初始化最小距离为无穷大
    best_idx = 0             # 初始化最佳质心索引
    
    for i, center in enumerate(c):  # 遍历所有质心
        dist = math.sqrt(sum((a - b) ** 2 for a, b in zip(x, center)))  # 计算欧几里得距离
        if dist < min_dist:  # 如果找到更近的质心
            min_dist = dist  # 更新最小距离
            best_idx = i     # 更新最佳索引
    
    return best_idx  # 返回最近质心的索引

def Kmeans(data, k, epsilon=0.001, max_iter=100):
    """
    K均值聚类主函数
    """
    centers = random.sample(data, k)  # 随机选择k个初始质心
    
    for it in range(max_iter):  # 开始迭代
        labels = [assign_cluster(p, centers) for p in data]  # 为每个点分配聚类标签
        
        new_centers = []  # 创建新质心列表
        for i in range(k):  # 遍历每个聚类
            points = [data[j] for j, label in enumerate(labels) if label == i]  # 获取属于当前聚类的所有点
            if points:  # 如果聚类不为空
                new_center = [sum(dim) / len(points) for dim in zip(*points)]  # 计算各维度均值作为新质心
                new_centers.append(new_center)  # 添加到新质心列表
            else:  # 如果聚类为空
                new_centers.append(random.choice(data))  # 随机选择一个点作为质心
        
        max_move = max(math.sqrt(sum((a - b) ** 2 for a, b in zip(old, new)))  # 计算质心移动的最大距离
                      for old, new in zip(centers, new_centers))
        
        centers = new_centers  # 更新质心
        
        if max_move < epsilon:  # 检查是否收敛
            break  # 如果收敛则提前结束
    
    return centers, labels  # 返回最终质心和标签

if __name__ == "__main__":
    data = [[1, 1], [1, 2], [2, 1], [2, 2], [8, 8], [8, 9], [9, 8], [9, 9]]  # 创建测试数据
    
    centers, labels = Kmeans(data, k=2)  # 运行K均值聚类
    
    print("最终质心:", centers)  # 打印质心
    print("各点标签:", labels)   # 打印标签